import common.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

/**
 * 101. Symmetric tree 对称二叉树
 * https://leetcode-cn.com/problems/symmetric-tree/
 */
class SymmetricTree {

    /**
     * 方法：递归判断左右子树是否对称
     * 
     * Args:
     *   root: 二叉树的根节点
     * 
     * Returns:
     *   boolean: 如果二叉树是对称的返回true,否则返回false
     * 
     * Time: O(n), n为节点数,需要遍历所有节点
     * 
     * Space: O(h), h为树的高度,递归调用栈的空间
     */
    public boolean isSymmetric(TreeNode root) {
        return isSameTree(root.left, root.right);
    }

    private boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null || q == null) {
            return p == q;
        }
        return p.val == q.val && isSameTree(p.left, q.right) && isSameTree(p.right, q.left);
    }

    /**
     * 方法：迭代判断左右子树是否对称,使用队列实现层序遍历
     * 
     * Args:
     *   root: 二叉树的根节点
     * 
     * Returns:
     *   boolean: 如果二叉树是对称的返回true,否则返回false
     * 
     * Time: O(n), n为节点数,需要遍历所有节点
     * 
     * Space: O(w), w为树的最大宽度,队列中最多存储一层的节点数
     */
    public boolean isSymmetric1(TreeNode root) {
        return check(root, root);
    }

    private boolean check(TreeNode p, TreeNode q) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(p);
        queue.offer(q);
        while (!queue.isEmpty()){
            p = queue.poll();
            q = queue.poll();
            if (p == null && q == null){
                continue;
            }
            if((p == null || q == null) || (p.val != q.val)){
                return false;
            }
            queue.offer(p.left);
            queue.offer(q.right);

            queue.offer(p.right);
            queue.offer(q.left);
        }
        return true;
    }
}